/*
快排+二分
经过一个快排，使得大元素在左边，小元素在右边，得一个pivot
如果pivot-low+1=k,那么pivot即为所求
如果pivot-low+1>k,说明第K大的元素在左半边，更新high=pivot-1;
如果pivot-low+1<k，说明第K大的元素在右半边，更新low=pivot+1;同时k=k-(pivot-low+1)
*/
class Solution {
public:
    int partition(vector<int>&a,int low,int high)
    {
        int pivot=a[low];
        while(low<high)
        {
            while(low<high&&a[high]<=pivot) high--;
            swap(a[low],a[high]);
            while(low<high&&a[low]>=pivot) low++;
            swap(a[low], a[high]);
        }
        return low;
    }
    int quicksort(vector<int>&a,int low,int high,int k)
    {
        int p=partition(a,low, high);
        if(k==p-low+1)
            return a[p];
        else if(p-low+1>k)
            return quicksort(a, low, p-1, k);
        else
            return quicksort(a, p+1, high, k-(p-low+1));
    }
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return quicksort(a, 0, n-1, K);
    }
};